//
// Created by Mr.J on 2019/11/2.
//

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

bool help(int i,int j,int k,string& s1,string&s2,string&s3){
    if((i==s1.size()&&k==s3.size()) || (j==s2.size()&&k==s3.size()))return true;
    return (s3[k]==s1[i] && help(i+1,j,k+1,s1,s2,s3))
    || (s3[k]==s2[j] && help(i,j+1,k+1,s1,s2,s3));
}

bool isInterleave(string s1, string s2, string s3) {
    if(s3.size() != s1.size()+s2.size())return false;
    return help(0,0,0,s1,s2,s3);
}

bool isInterleave1(string s1, string s2, string s3){
    short l1 = s1.size(),l2 = s2.size(),l3 = s3.size();
    if(l3 != l1+l2)return false;
    bool dp[l1+1][l2+1];
    memset(dp,false, sizeof(dp));
    dp[0][0] = true;

    for (int i = 0; i < l1; ++i) {
        for (int j = 0; j < l2; ++j) {
            if(i==0&&j==0)dp[i][j] = true;
            else if(i == 0)dp[i][j] = s2[j-1]==s3[i+j-1]&&dp[i][j-1];
            else if(j == 0)dp[i][j] = s1[i-1]==s3[i+j-1]&&dp[i-1][j];
            else dp[i][j] = (s1[i-1]==s3[i+j-1]&&dp[i-1][j])||(s2[j-1]==s3[i+j-1]&&dp[i][j-1]);
        }
    }
    return dp[l1][l2];
}

int main(){
    string s1 = "a",s2 = "",s3 = "c";
    cout<<isInterleave(s1,s2,s3)<<endl;
    return 0;
}